package com.jeff.test;

import java.util.Arrays;

/**
 * 给定两个有序数组,不使用临时数组的情况下进行合并
 * @author yaojianfeng
 */
public class MergeSortedArray {
    public void merge(int[] arrA, int[] arrB) {
        // 获取两个数组的长度
        int oldA = arrA.length;
        int n = arrB.length;

        // 对数组A的长度进行扩展,扩展为能容纳下原始的数组A和数组B
        int m = oldA + n;
        arrA = Arrays.copyOf(arrA, m);

        // 初始化两个指针，分别指向arrA和arrB的末尾
        int indexA = oldA - 1;
        int indexB = n - 1;
        // 初始化合并后数组的末尾索引
        int mergeIndex = m  - 1;

        // 当两个数组都有剩余元素时，比较并选择较大的元素放入arrA的末尾
        while (indexA >= 0 && indexB >= 0) {
            if (arrA[indexA] > arrB[indexB]) {
                arrA[mergeIndex] = arrA[indexA];
                indexA--;
            } else {
                arrA[mergeIndex] = arrB[indexB];
                indexB--;
            }
            mergeIndex--;
        }

        // 如果arrB还有剩余元素，直接复制到arrA的前面
        while (indexB >= 0) {
            arrA[mergeIndex] = arrB[indexB];
            indexB--;
            mergeIndex--;
        }
        System.out.println(Arrays.toString(arrA));
    }

    public static void main(String[] args) {
        int[] arrA = {1, 3, 5, 7, 9};
        int[] arrB = {2, 4, 6, 8};

        MergeSortedArray solution = new MergeSortedArray();
        solution.merge(arrA, arrB);

    }
}
